package oj;

import java.util.*;

public class Solution {
    //只出现一次的数字
    public static int singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int x: nums){
            if(set.contains(x)){
                set.remove(x);
            }else{
                set.add(x);
            }
        }
        for(int x: nums){
            if(set.contains(x)){
                return x;
            }
        }
        return -1;
    }

    //宝石与石头
    public static int numJewelsInStones(String jewels, String stones) {
        HashSet<Character> set = new HashSet<>();
        int count = 0;
        for(char ch: jewels.toCharArray()){//宝石放入集合
            set.add(ch);
        }
        for(char ch: stones.toCharArray()){//辨别石头是否为宝石
            if(set.contains(ch)){
                count++;
            }
        }
        return count;
    }

    //坏键盘
    private static void func(String str1, String str2){//str1 预期输出 str2实际输出
        HashSet<Character> set = new HashSet<>();
        for(char ch: str2.toUpperCase().toCharArray()){
            set.add(ch);
        }
        HashSet<Character> set2 = new HashSet<>();
        for(char ch: str1.toUpperCase().toCharArray()){
            if(!set.contains(ch) && !set2.contains(ch)){
                System.out.print(ch);
                set2.add(ch);

            }
        }


    }
    //复制随机链表
//    public Node copyRandomList(Node head) {
//        Map<Node,Node> map = new HashMap<>();
//        Node cur = head;
//        while(cur != null){//1. 存储对应关系
//            Node node = new Node(cur.val);
//            map.put(cur,node);
//            cur = cur.next;
//        }
//        //2. 第二次遍历链表 开始修改每个节点的指向
//        cur = head;
//        while(cur != null){
//            map.get(cur).next = map.get(cur.next);
//            map.get(cur).random = map.get(cur.random);
//            cur = cur.next;
//        }
//        return map.get(head);
//    }

    /**
     * 统计单词出现的次数
     * @param words
     * @param k
     * @return
     */
    public List<String> topKFrequent(String[] words, int k) {
        //1. 先统计单词出现的次数
        Map<String,Integer> map = new HashMap<>();
        for (String word: words) {
            if (map.get(word) == null){
                map.put(word,1);
            }else{
                int val = map.get(word)+1;
                map.put(word,val);
            }
        }
        //2. 遍历统计好的Map，把每组数据存储到小根堆
        PriorityQueue<Map.Entry<String,Integer>> heap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0){
                    //放元素的时候，如果频率相同，我们转换为大根堆
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        for (Map.Entry<String, Integer> entry: map.entrySet()) {
            if (heap.size() < k){
                heap.offer(entry);
            }else {
                //找堆顶元素
                Map.Entry<String, Integer> top = heap.peek();
                if (top.getValue().compareTo(entry.getValue()) < 0){
                    heap.poll();
                    heap.offer(entry);
                }else {
                    //按字典序排序
                    if (top.getValue().compareTo(entry.getValue()) == 0){
                        if (top.getKey().compareTo(entry.getKey()) > 0){
                            heap.poll();
                            heap.offer(entry);
                        }
                    }
                }

            }
        }
        //放到了小根堆
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String, Integer> top = heap.poll();
            ret.add(top.getKey());
        }
        //逆置
        Collections.reverse(ret);
        return ret;

    }
}
